#include "headfiles.h"

using namespace std;

GraphNode *cloneGraph(GraphNode *root) {
    if (root == NULL) {
        return NULL;
    }

    map<GraphNode *, GraphNode *> node_map;
    queue<GraphNode *> node_queue;
    GraphNode *tmp_node = new GraphNode;
    if (tmp_node == NULL) {
        return NULL;
    }

    *tmp_node = *root;
    tmp_node->neighbors.clear();
    node_map[root] = tmp_node;
    node_queue.push(root);

    while (!node_queue.empty()) {
        GraphNode *node = node_queue.front();
        node_queue.pop();

        for (auto it = node->neighbors.begin(); it != node->neighbors.end(); it++) {
            auto nit = node_map.find(*it);
            if (nit == node_map.end()) {
                node_queue.push(*it);
                GraphNode *neighbor_node = new GraphNode;
                *neighbor_node = **it;
                neighbor_node->neighbors.clear();
                node_map[node]->neighbors.push_back(neighbor_node);
                node_map[*it] = neighbor_node;
            }
            else {
                node_map[node]->neighbors.push_back(node_map[*it]);
            }
        }
    }

    return tmp_node;
}
